4742. Number of divisors
One integer n is given. Find the number of its
divisors, excluding divisors n and 1.
Input. One
positive integer n (2 ≤ n ≤ 231 –
1).
Output. Print the
number of divisors of n.
|
Sample
input |
Sample
output |
|
18 |
4 |
SOLUTION
mathematics
Algorithm analysis
Let d(n) be the number of divisors of n. Obviously, d(1) = 1.
Let p be a prime integer. Then p has two divisors: 1 and p. Therefore, d(p) = 2.
Let n = pk be a power of a prime
number. Then n has k + 1 divisors: 1, p, p2, p3, …, pk. Hence, d(pk) = k + 1.
Let n = pkql. Consider two sets:
P ={1, p, p2, p3, …, pk } and Q ={1, q, q2, q3, …, ql }
Any divisor d of the number pkql can be represented in the
form x * y, where x ∈ P, y ∈
Q. A divisor x from P can be chosen in k + 1 ways, and a divisor y from Q can be chosen in l + 1 ways. Therefore, a divisor d = x * y can be formed in (k
+ 1) * (l + 1) ways.
Decompose the
number n into its prime factors: n = 
. The number of divisors of n is equal to
d(n) = (a1 + 1) * (a2
+ 1) * … * (ak + 1)
Example
The number n = 18 has 6 divisors: 1, 2, 3, 6, 9,
18.
Let’s decompose the number
n = 18 into its prime factors:
18 = 2 * 32
Therefore
d(18) = (1 + 1)
* (2 + 1) = 2 * 3 = 6
Subtracting two
divisors (1 and 18), we get the answer: 4 divisors.
Algorithm realization
The function CountDivisors decomposes the number n into its prime factors and calculates the number of its
divisors d(n).
int CountDivisors(int n)
{
int c, i, res
= 1;
for(i = 2; i
* i <= n; i++)
{
if (n % i
== 0)
{
c = 0;
while(n %
i == 0)
{
n /= i;
c++;
}
res *= (c + 1);
}
}
if (n > 1)
res *= 2;
return res;
}
The main part of the
program. Read the value
of n.
scanf("%d",&n);
Calculate and print the answer.
From the total number of divisors d(n) subtract two
divisors: 1 and the number n itself.
printf("%d\n",CountDivisors(n)-2);
Python realization
import math
The function CountDivisors decomposes the number n into its prime factors and calculates the number of its
divisors d(n).
def CountDivisors(n):
res = 1;
for i in range(2, int(math.sqrt(n)) + 1):
if (n % i == 0):
c = 0
while (n % i == 0):
n //= i
c += 1
res *= (c + 1);
if (n > 1): res *= 2;
return res;
The main part of the
program. Read the value
of n.
n = int(input())
Calculate and print the answer.
From the total number of divisors d(n) subtract two
divisors: 1 and the number n itself.
print(CountDivisors(n) - 2)